package Classic150;

import Tree.TreeNode;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

public class 二叉搜索树迭代器 {
    /*
        进阶：next() 和 hasNext() 操作均摊时间复杂度为 O(1) ，并使用 O(h) 内存，其中 h 是树的高度
     */
    class BSTIterator {
        private TreeNode cur;
        private Stack<TreeNode> stack;

        public BSTIterator(TreeNode root) {
            cur = root;
            stack = new Stack<>();
        }

        public int next() {
            while (cur != null) {
                stack.push(cur);
                cur = cur.left;
            }
            cur = stack.pop();
            int ret = cur.val;
            cur = cur.right;
            return ret;
        }

        public boolean hasNext() {
            return cur != null || !stack.isEmpty();
        }
    }

    /*
        普通：空间换时间
     */
    /*class BSTIterator {
        private int cur;
        private List<Integer> list;

        public BSTIterator(TreeNode root) {
            cur = 0;
            list = new ArrayList<>();
            inorder(root);
        }

        private void inorder(TreeNode root) {
            if (root == null) return;
            inorder(root.left);
            list.add(root.val);
            inorder(root.right);
        }

        public int next() {
            return list.get(cur++);
        }

        public boolean hasNext() {
            return cur < list.size();
        }
    }*/
}
